/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class StrangePrinter {
    public int strangePrinter(String s) {
    	int n=s.length();
    	if(n==0){
    		return 0;
    	}
    	int[] pos=new int[26];
    	int[] oldP=new int[n];
    	for (int i = 0; i < 26; i++) {
    		pos[i]=-1;
		}
    	for (int i = 0; i < n; i++) {
    		oldP[i]=pos[s.charAt(i)-'a'];
    		pos[s.charAt(i)-'a']=i;
		}
    	int[][] dp=new int[n][n];
    	for (int i = n-1; i >=0; i--) {
    		for (int j = i; j < n; j++) {
    			dp[i][j]=i==j?1:dp[i][j-1]+1;
    			for (int k = j-1; k >=i; k--) {
    				if(s.charAt(k)==s.charAt(j)){
    					dp[i][j]=Math.min(dp[i][j], dp[i][k]+dp[k+1][j-1]);
//        				break;
    				}
				}
			}
		}
        return dp[0][n-1];
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String string="dddccbdbababaddcbcaabdbdddcccddbbaabddb";
		System.out.println(new StrangePrinter().strangePrinter(string));
	}

}
